package lyl.tree;

import java.util.ArrayList;
import java.util.List;

public class SerializeAndDeserialize {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public String serialize(TreeNode root) {
        if(root == null){
            return "[]";
        }
        List<TreeNode> list = new ArrayList<>();
        list.add(root);
        for (int i = 0; i < list.size(); i++) {
            TreeNode node = list.get(i);
            if(node == null){
                continue;
            }
            list.add(node.left);
            list.add(node.right);
        }
        while(list.get(list.size() - 1) == null){
            list.remove(list.size() - 1);
        }
        StringBuilder sb = new StringBuilder("[");
        sb.append(list.get(0).val);
        for (int i = 1; i < list.size(); i++) {
            TreeNode node = list.get(i);
            if(node == null ){
                sb.append(",null");
            }else {
                sb.append(",").append(node.val);
            }
        }
        sb.append("]");
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public  TreeNode deserialize(String data) {
        if(data == null || data.equals("[]")){
            return null;
        }
        String[] split = data.substring(1, data.length() - 1).split(",");
        TreeNode node = new TreeNode(Integer.parseInt(split[0]));
        List<TreeNode> queue = new ArrayList<>();
        queue.add(node);

        int index = 0; // 根节点
        boolean isLeft = true;
        for (int i = 1;i<split.length ; i++) {

            if(!split[i].equals("null")){
                TreeNode leafNode = new TreeNode(Integer.parseInt(split[i]));
                if(isLeft){
                    queue.get(index).left = leafNode;
                }else {
                    queue.get(index).right = leafNode;
                }
                queue.add(leafNode);
            }
            if(!isLeft){
                index ++; //判断下一个根节点
            }
            isLeft = !isLeft;

        }

        return queue.get(0);

    }

    public static void main(String[] args) {
        SerializeAndDeserialize serializeAndDeserialize = new SerializeAndDeserialize();
        TreeNode deserialize = serializeAndDeserialize.deserialize("[1,2,3,null,null,4,5,6,7]");
        System.out.println(serializeAndDeserialize.serialize(deserialize));
    }

}
